/*
 * Copyright Radosław Smogura, 2012. All rights reserved.
 *
 * The content of this file is confidential and it is intelectual property
 * of copyright owners.
 * 
 *
 * $URL: http://reprap-ide.googlecode.com/svn/trunk/RepRapIDE/RepRapProject/src/main/java/eu/softper/reprap/generator/InfillGenerator.java $
 * $Id: InfillGenerator.java 3 2012-11-19 10:58:30Z mail@smogura.eu $
 * $Revision: 3 $
 */
package eu.softper.reprap.generator;

import eu.softper.reprap.utils.HashMapCustomized;
import java.math.BigDecimal;
import java.util.*;

/** Generator for infill lines for given layer. The additional properties like 
 * line radius, infill angle must be supplied.
 *
 * @author Radosław Smogura
 */
public class InfillGenerator<T extends Number & Comparable<T>> {
    private T ONE;
    private T TWO;
    private T DEG_90;
    private T DEG_180;
    private T DEG_270;
    private T DEG_360;
    
    private InfillGeneratorConfig config;
    
    private ArrayList<RotatedLine<T>> rotations;
    private Layer<T> layer;
    
    private T minY, maxY;
    private NumericFactory<T> nf;
    public InfillGenerator(NumericFactory<T> nf, Layer<T> layer, InfillGeneratorConfig config) {
        this.layer = layer;
        this.config = config;        
        this.nf = nf;
        
        ONE = nf.valueOf(1);
        TWO = nf.valueOf(2);
        DEG_90 = nf.valueOf(90);
        DEG_180 = nf.valueOf(180);
        DEG_270 = nf.valueOf(270);
        DEG_360 = nf.valueOf(360);
    }
    
    
    private List<SceneLine<T>> infills = new LinkedList<SceneLine<T>>();
    
    /** Rotates vertex around (0,0) the sin cos params are values of angle.
     * 
     */
    private DecimalVertex<T> rotateVertex(DecimalVertex<T> vertex, T sinPlus, T sinMinus, T cosPlus, T cosMinus) {
        T x = vertex.getX();
        T y = vertex.getY();
        T xR = nf.add(nf.mul(x, cosPlus), nf.mul(y, sinMinus));
        T yR = nf.add(nf.mul(x, sinPlus), nf.mul(y, cosPlus));
        
        if (minY == null)
            minY = yR;
        if (maxY == null)
            maxY = yR;
        minY = nf.min(minY, yR);
        maxY = nf.max(maxY, yR);
        
        //TODO Add scaling - rethink if it's needed
        //TODO Avoid function call in getZPos;
        return new DecimalVertex<T>(xR, yR, nf.valueOf(layer.getzPos()));
    }
    
    private List<SceneLine<T>> derotateLines(List<SceneLine<T>> lines) {
        final double angle = -(config.getAngle().doubleValue() * Math.PI / 180);
        
        final T sinPlus = nf.valueOf(Math.sin(angle));
        final T cosPlus = nf.valueOf(Math.cos(angle));
        final T sinMinus = nf.negate(sinPlus);
        final T cosMinus = nf.negate(cosPlus);
        
        ArrayList<SceneLine<T>> out = new ArrayList<SceneLine<T>>(lines.size());
        
        for(SceneLine<T> l : lines) {
            //TODO Cache some rotations, for boxes those will be same for layer and layer + 2
            DecimalVertex<T> v1 = rotateVertex(l.getV1(), sinPlus, sinMinus, cosPlus, cosMinus);
            DecimalVertex<T> v2 = rotateVertex(l.getV2(), sinPlus, sinMinus, cosPlus, cosMinus);
            
            out.add(new SceneLine(v1, v2));
        }
        
        return out;
    }
    
    private void rotateAndSortLayer() {
        final double angle = config.getAngle().doubleValue() * Math.PI / 180;
        
        final T sinPlus = nf.valueOf(Math.sin(angle));
        final T cosPlus = nf.valueOf(Math.cos(angle));
        final T sinMinus = nf.negate(sinPlus);
        final T cosMinus = nf.negate(cosPlus);
        
        //1. Perform rotations
        int outlinesCount = 0;
        for (List<?> l : layer.getReducedOutlines())
            outlinesCount += l.size();
        
        ArrayList<RotatedLine<T>> rotations = new ArrayList<RotatedLine<T>>(outlinesCount);
        
        final DecimalVertex.DictionaryComparator comparator = DecimalVertex.DictionaryComparator.SHARED_INSTANCE;
        
        for (List<SceneLine<T>> outline : layer.getReducedOutlines()) {
            for(SceneLine<T> l : outline) {
                if (l.getLineType() != SceneLineType.OUTLINE)
                    continue;
                
                //TODO Cache some rotations, for boxes those will be same for layer and layer + 2
                DecimalVertex<T> v1 = rotateVertex(l.getV1(), sinPlus, sinMinus, cosPlus, cosMinus);
                DecimalVertex<T> v2 = rotateVertex(l.getV2(), sinPlus, sinMinus, cosPlus, cosMinus);
                boolean v1Less = comparator.compare(v1, v2) <= 0;

                SceneLine rotatedLine = new SceneLine(
                        v1Less ? v1 : v2,
                        v1Less ? v2 : v1);        
                RotatedLine<T> rl = new RotatedLine(l, rotatedLine);

                if (Math.abs(rl.getRotatedLine().getMaxY().doubleValue() - 47.764) < 0.001) {
                    if (layer.getNumber() == 7)
                        rl.hashCode();
                }
                for (T a : l.getXyNormalsAngles()) {
                    T ra = nf.degreeAsRemainder(nf.add(a, nf.valueOf(config.getAngle())));

                    if (nf.isNotZero(nf.reminder(ra, DEG_90))) {
                        rl.getRotatedAngles().add(ra);
                    }else if (!nf.isNotZero(nf.reminder(ra, DEG_180))) {
                        rl.getRotatedAngles().add(ra);
                    }else {
                        //This may mean we have rounding problem here, from this
                        //stage we require only non-vertical lines, so
                        //compare if those are not vertical and recalculate angle
                        //if needed
                        T _maxY = rl.getRotatedLine().getMaxY();
                        T _minY = rl.getRotatedLine().getMinY();
                        if (_maxY.compareTo(_minY) != 0) {
                            double m1, m2;
                            m1 = _minY.doubleValue();
                            m2 = _maxY.doubleValue();

                            double y =  m1 - m2;
                            double x = Math.abs(rl.getRotatedLine().getV1().getX().doubleValue() -
                                    rl.getRotatedLine().getV2().getX().doubleValue());
                            double radAngle = Math.atan2(y, x);
                            double degAngle = radAngle * 180.0 / Math.PI;
                            int quarter = (int) nf.div(ra, DEG_90).doubleValue();
                            degAngle += 90.0 * quarter;

                            T newAngle = nf.degreeAsRemainder(nf.valueOf(degAngle));
                            rl.getRotatedAngles().add(newAngle);
                        }
                    }
                }
                rotations.add(rl);
            }
        }
        
        //2. Sort rotations
        Collections.sort(rotations, RotatedLine.ByRotationYComparator.SHARED_INSTANCE);
        
        //3. Copy this to linked list
        this.rotations = rotations;
    }
    
    private DecimalVertex intersectLineAt(SceneLine<T> sl, T lineY) {
        // x = sl.v1.x*t + sl.v2.x(1-t)
        // lineY = s1.v1.y*t + s1.v2.y(1-t) -> t = (lineY - s1.v2.y) / (s1.v1.y - s1.v2.y)
        
        T divisor = nf.subs(sl.getV1().getY(), sl.getV2().getY());
        if (!nf.isNotZero(divisor)) {
            divisor.hashCode();
        }
        T t = nf.div(nf.subs(lineY, sl.getV2().getY()), divisor);
        T x = nf.add(nf.mul(sl.getV1().getX(), t),
                nf.mul(sl.getV2().getX(), nf.subs(ONE, t)));
        
        return new DecimalVertex(x, lineY, sl.getV1().getZ());
    }
    
    private int passNo;
    private void calculateInfill(LinkedList<RotatedLine<T>> linesOfInterest, T start, T end) {
        T zPos = nf.valueOf(layer.getzPos());
        
        passNo++;
        

        
        //1. Calulate different points of line
        List<RotatedLineSlice> infillPoints = new LinkedList<RotatedLineSlice>();
        Map<T, Integer> subslices = 
                new HashMapCustomized<T, Integer>(new HashMapCustomized.NumberEqualityProvider(100.0));
        
        T lineMiddle = nf.div(nf.add(start, end), TWO);
        
        //Debug lines
        if (layer.getNumber() == 6 && lineMiddle.doubleValue() >= -31.8 && lineMiddle.doubleValue() <= -30.8) {
            new Object().hashCode();
        }
        
        for(RotatedLine rl : linesOfInterest) {
            if (rl.getRotatedAngles().size() == 0)
                continue;
            SceneLine<T> rotated = rl.getRotatedLine(); //Avoid function calls
            
            if (rotated.getMaxY().compareTo(rotated.getMinY()) == 0)
                continue;
            
            //For each rotated line calculate line begin and end with respect
            //to horizontal boundaries - if one edge of line crossed boundaries
            //(start; end) then it's min, max - otherwise left, right may be min
            //max
            final int startCmp = rotated.getMinY().compareTo(start);
            final int endCmp = rotated.getMaxY().compareTo(end);
            
            RotatedLineSlice slice = new RotatedLineSlice(rl);
            DecimalVertex<T> v1, v2;
            if (startCmp < 0) {
                v1 = intersectLineAt(rotated, start);
            }else {
                v1 = rotated.getMinYVertex();
            }
            
            if (endCmp > 0) {
                v2 = intersectLineAt(rotated, end);
            }else {
                v2 = rotated.getMaxYVertex();
            }
            
            if (DecimalVertex.DictionaryComparator.SHARED_INSTANCE.compare(v1, v2) > 0) {
                DecimalVertex tmp = v2;
                v2 = v1;
                v1 = tmp;
            }
            
            Iterator<T> angles = rl.getRotatedAngles().iterator();
            T angle = angles.next();
            
            subslices.put(v1.getY(), Integer.valueOf(0));
            subslices.put(v2.getY(), Integer.valueOf(0));


            slice.setSlice(new SceneLine(v1, v2));
            
            if (DEG_90.compareTo(angle) > 0 || DEG_270.compareTo(angle) < 0) {
                slice.setOpening(false);
            }else {
                slice.setOpening(true);
            }
            
            infillPoints.add(slice);
        }
        
        subslices.put(start, Integer.valueOf(0));
        subslices.put(end, Integer.valueOf(0));
        
        infillPoints = new ArrayList<RotatedLineSlice>(infillPoints);
        Collections.sort(infillPoints, RotatedLineSlice.ByV1XComparator.INSATNCE);

        if (infillPoints.isEmpty())
            return;
        
        T pointStart = null;
        RotatedLineSlice<T> tmpSlice = infillPoints.iterator().next();
        
        T maxPoint = tmpSlice.getSlice().getMaxX();
//        T minPoint = tmpSlice.getSlice().getMinX();
        
        for (RotatedLineSlice<T> s : infillPoints) {
            int nonZeroEntries = 0;
            for (Map.Entry<T, Integer> e : subslices.entrySet()) {
                int val = e.getValue();
                if (e.getKey().compareTo(s.getSlice().getMaxY()) < 0 &&
                        e.getKey().compareTo(s.getSlice().getMinY()) >= 0) {
                    if (s.isOpening())
                        //val = 1;
                        val++;
                    else
                        //val = 0; //--;
                        val--;
                    if (val > 0)
                        nonZeroEntries++;
                    e.setValue(val);
                }else {
                    if (val == 1)
                        nonZeroEntries++;
                }
            }
            maxPoint = nf.max(maxPoint, s.getSlice().getMaxX());
//            minPoint = nf.min(minPoint, s.getSlice().getMinX());
            
            if (nonZeroEntries == subslices.size() - 1) {
                if (pointStart == null) {
                    pointStart = 
                            maxPoint;
                            //nf.div(nf.add(s.getSlice().getV1().getX(), s.getSlice().getV2().getX()), TWO);
                    //pointStart = nf.max(s.getSlice().getV1().getX(), s.getSlice().getV2().getX());
                }
            }else {
                if (pointStart != null) {
                    //T pointEnd = nf.min(s.getSlice().getV1().getX(), s.getSlice().getV2().getX());
                    T pointEnd = nf.div(nf.add(s.getSlice().getV1().getX(), s.getSlice().getV2().getX()), TWO);
                    if (pointStart.compareTo(pointEnd) < 0) {
                        boolean x = true;
                        if (x)
                        infills.add(new SceneLine<T>(
                                new DecimalVertex<T>(pointStart, lineMiddle, zPos),
                                new DecimalVertex<T>(pointEnd, lineMiddle, zPos)
                                ));
                    }
                    pointStart = null;
                }
            }
        }
    }
    
    public void generateInfill() {
        rotateAndSortLayer();
        
        LinkedList<RotatedLine<T>> linesOfInterest = new LinkedList<RotatedLine<T>>();
        
        //To avoid function call;
        
        final BigDecimal step = config.getStep();        
        final BigDecimal radius = config.getRadius();
        
        if (minY == null) {
            //Layer is empty, may sometimes happen
            return;
        }
        
        T start = minY;
        T end = nf.add(start, nf.add(nf.valueOf(radius), nf.valueOf(radius)));
        
        Iterator<RotatedLine<T>> rotationI = rotations.iterator();
        RotatedLine<T> stackLine = rotationI.next();
        
            
            passNo = 0;
        while (end.compareTo(maxY) <= 0) {
            //1. Add new lines of interest
            while (stackLine != null) {
                //2012-11-07: It was funny I wrote if (stackLine.getRotatedAngles().size() > 0 && end.compareTo)
                //Debugging taken about hour
                //generation was sometimes interesting... ofcourse without next
                //when isEmpty on first element next will be never taken.
                if (stackLine.getRotatedAngles().isEmpty()) {
                    if (rotationI.hasNext())
                        stackLine = rotationI.next();
                    else
                        stackLine = null;
                    continue;
                }else if (end.compareTo(stackLine.getRotatedLine().getMinY()) > 0) {
                    linesOfInterest.add(stackLine);
                    if (rotationI.hasNext())
                        stackLine = rotationI.next();
                    else
                        stackLine = null;
                }else {
                    //Lines are ordered by it's minY
                    break;
                }
            }
            
            //2. Remove lines that are not in interest scope
            Iterator<RotatedLine<T>> ii = linesOfInterest.iterator();
            while (ii.hasNext()) {
                RotatedLine<T> rl = ii.next();
                if (start.compareTo(rl.getRotatedLine().getMaxY()) >= 0)
                    ii.remove();
            }
            //3. And now start hard playing
            calculateInfill(linesOfInterest, start, end);
            
            start = nf.add(start, nf.valueOf(step));
            end = nf.add(end, nf.valueOf(step));
        }
        
        //4. Derotate infills
        layer.setInfills(derotateLines(infills));
        this.infills = null;
    }
    
    private static class RotatedLineSlice<T extends Number & Comparable<T>> {
        private RotatedLine rotatedLine;
        private SceneLine<T> slice;
        private boolean opening;
        
        public RotatedLineSlice(RotatedLine rotatedLine) {
            this.rotatedLine = rotatedLine;
        }

        public RotatedLine getRotatedLine() {
            return rotatedLine;
        }

        public void setRotatedLine(RotatedLine rotatedLine) {
            this.rotatedLine = rotatedLine;
        }

        public SceneLine<T> getSlice() {
            return slice;
        }

        public void setSlice(SceneLine<T> slice) {
            this.slice = slice;
        }

        public void setOpening(boolean opening) {
            this.opening = opening;
        }

        public boolean isOpening() {
            return opening;
        }
        
        public static class ByV1XComparator<T extends Number & Comparable<T>> implements Comparator<RotatedLineSlice<T>> {
            public static final ByV1XComparator INSATNCE = new ByV1XComparator();
            
            @Override
            public int compare(RotatedLineSlice<T> o1, RotatedLineSlice<T> o2) {
                return o1.getSlice().getV1().getX().compareTo(o2.getSlice().getV1().getX());
            }
            
        }

        @Override
        public String toString() {
            return (opening ? "> " : "< ") + slice.toString();
        }
    }
    
    private static class RotatedLine<T extends Number & Comparable<T>> {
        private SceneLine<T> originalLine;
        private SceneLine<T> rotatedLine;

        private Set<T> rotatedAngles = new HashSet<T>();
        
        public RotatedLine(SceneLine<T> originalLine, SceneLine<T> rotatedLine) {
            this.originalLine = originalLine;
            this.rotatedLine = rotatedLine;
        }

        public Set<T> getRotatedAngles() {
            return rotatedAngles;
        }

        public SceneLine<T> getOriginalLine() {
            return originalLine;
        }

        public void setOriginalLine(SceneLine<T> originalLine) {
            this.originalLine = originalLine;
        }

        public SceneLine<T> getRotatedLine() {
            return rotatedLine;
        }

        public void setRotatedLine(SceneLine<T> rotatedLine) {
            this.rotatedLine = rotatedLine;
        } 
    
        public static class ByRotationYComparator<T extends Number & Comparable<T>> implements Comparator<RotatedLine> {

            private static final SceneLine.ByYComparator BY_Y_COMPARATOR = SceneLine.ByYComparator.SHARED_INSTANCE;
            public static final ByRotationYComparator SHARED_INSTANCE = new ByRotationYComparator();

            @Override
            public int compare(RotatedLine o1, RotatedLine o2) {
                return BY_Y_COMPARATOR.compare(o1.getRotatedLine(), o2.getRotatedLine());
            }
        }

        @Override
        public String toString() {
            return rotatedLine.toString();
        }
    }
}
